package com.leetcode.algs4.graph;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/6/16 15:41
 */
public class DirectedCycle {

    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle; // 如果有环，创建这个环
    private boolean[] onStack; // 保存递归调用时，栈上的所有顶点

    public DirectedCycle(Digraph G) {
        onStack = new boolean[G.V()];
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) dfs(G, v);
        }
    }

    private void dfs(Digraph G, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (this.hasCycle()) return;
            else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
            // 如果没有环，那么一次出栈，不会再找到已在栈上的节点
            // 如果找到了，那么证明图中有环的存在
            else if (onStack[w]) {
                cycle = new Stack<>();
                // 构建这个环，依次获取DFS中顶点的上级顶点
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }

}
